package gold.digger;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC639 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目参考了别人代码
     * 不是因为复杂，而是因为经典
     * 未来需要再次复习此道题目
     * 作者：AC_OIer
       链接：https://leetcode-cn.com/problems/decode-ways-ii/solution/gong-shui-san-xie-fen-qing-kuang-tao-lun-902h/
     * @return:
     */
    class Solution {
        int mod = (int) 1e9 + 7;

        public int numDecodings(String s) {
            char[] cs = s.toCharArray();
            int n = cs.length;
            long[] f = new long[n];
            f[0] = cs[0] == '*' ? 9 : (cs[0] != '0' ? 1 : 0);
            for (int i = 1; i < n; i++) {
                char c = cs[i], prev = cs[i - 1];
                if (c == '*') {
                    // cs[i] 单独作为一个 item
                    f[i] += f[i - 1] * 9;
                    // cs[i] 与前一个字符共同作为一个 item
                    if (prev == '*') {
                        // 11 - 19 & 21 - 26
                        f[i] += (i - 2 >= 0 ? f[i - 2] : 1) * 15;
                    } else {
                        int u = (int) (prev - '0');
                        if (u == 1) {
                            f[i] += (i - 2 >= 0 ? f[i - 2] : 1) * 9;
                        } else if (u == 2) {
                            f[i] += (i - 2 >= 0 ? f[i - 2] : 1) * 6;
                        }
                    }
                } else {
                    int t = (int) (c - '0');
                    if (prev == '*') {
                        if (t == 0) {
                            f[i] += (i - 2 >= 0 ? f[i - 2] : 1) * 2;
                        } else {
                            // cs[i] 单独作为一个 item
                            f[i] += f[i - 1];
                            // cs[i] 与前一个字符共同作为一个 item
                            if (t <= 6) {
                                f[i] += (i - 2 >= 0 ? f[i - 2] : 1) * 2;
                            } else {
                                f[i] += i - 2 >= 0 ? f[i - 2] : 1;
                            }
                        }
                    } else {
                        int u = (int) (prev - '0');
                        if (t == 0) {
                            if (u == 1 || u == 2) {
                                f[i] += i - 2 >= 0 ? f[i - 2] : 1;
                            }
                        } else {
                            // cs[i] 单独作为一个 item
                            f[i] += (f[i - 1]);
                            // cs[i] 与前一个字符共同作为一个 item
                            if (u == 1) {
                                f[i] += i - 2 >= 0 ? f[i - 2] : 1;
                            } else if (u == 2 && t <= 6) {
                                f[i] += i - 2 >= 0 ? f[i - 2] : 1;
                            }
                        }
                    }
                }
                f[i] %= mod;
            }
            return (int) (f[n - 1]);
        }
    }


    class Solution_Slow_Mind {

        int factor = 1000000007;

        public int numPara(String s) {
            if (s.length() <= 1) return s.charAt(0) == '*' ? 9 : 1;

            long[] dp = new long[s.length()];
            dp[s.length() - 1] = s.charAt(s.length() - 1) == '*' ? 9 : 1;

            for (int i = s.length() - 2; i >= 0; i--) {
                if (s.charAt(i) == '1') {
                    dp[i] = 2 * dp[i + 1] % factor;
                } else if (s.charAt(i) == '2') {
                    if (s.charAt(i + 1) >= '1' && s.charAt(i + 1) <= '6') dp[i] = 2 * dp[i + 1] % factor;
                    else if (s.charAt(i + 1) == '*') ;
                }
            }

            return ((int) dp[0]);
        }
    }

    public void run() {
        Solution solution = new Solution();
        List<Integer> list = new ArrayList<>();
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC639 an = new LC639();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
